By yusijia

Updated:

Contents
  • 联想下小时候是怎样翻拼音字典
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


例如：输入
me
watch
me
while
输出有多少个单词

主要操作：

struct node{
    char a;                   //存字母
    struct node *next[26];   //代表26个字母    这个字母节点下的26个指针代表26个字母，如果 指针为空 说明没有出现这个字母（重点）
    int flag;                  //标记这个字母是一个单词的结尾
}root;

void insert(char s[])
{
    int len=strlen(s),i;
    struct node *p=&root;
    for(i = 0; i < len; i++)                // i = 0时，根root里面不存单词，所以看下一个节点。
    {
        if(p->next[s[i]-'a']==NULL)         //没出现过这个字母
        {
            p->next[s[i]-'a']=(struct node *)malloc(sizeof(struct node));   //插入新的字母，新节点
            memset(p->next[s[i]-'a']->next,0,sizeof(struct node *) * 26);    //这个字母后的新的next数组清零  nxet数组就像26个节点
        }
        p=p->next[s[i]-'a'];
    }
    if(p->flag != 1)                        //如果不是结尾    1代表是结尾
    {
        count++;                            //记一次数  说明出现了新单词
        p->flag=1;                          //把这个单词最后一个字母标记为结尾
    }
}
Contents